// 桶排序学习
#include <iostream>
#include <vector>
#include <list>

using namespace std;

const int M = 10; // 待排数组中元素最大值

vector<int> bucket_sort(int arr[], int N) {
    // 声明count数组, 包含M+1个桶, 每个桶初始为一个空链表
    vector<list<int>> count(M + 1);
    vector<int> result;
    int i;

    // 将N个数据放入桶中
    for (i = 0; i < N; i++) {
        count[arr[i]].push_front(arr[i]);
    }

    // 输出所有桶中的数据, 这里是放到一个vector中然后返回出去
    for (i = 0; i < M + 1; i++) {
        list<int> tmp = count[i];
        if (tmp.size() > 0) { // 如果某个桶不为空, 输入桶中所有元素
            for (list<int>::iterator iter = tmp.begin(); iter != tmp.end(); iter++) {
                result.push_back(*iter);
            }
        }
    }
    return result;
}

// 按`0-9`, `10-19`, .., `80-89`, `90-100`来分类
vector<int> bucket_sort2(int arr[], int N) {
    const int bucketNum = 10; // 桶个数
    vector<list<int>> count(bucketNum);
    vector<int> result;
    list<int> tmp;
    int i;

    for (i = 0; i < N; i++) {
        int bucketIndex = arr[i] / 10;
        if (bucketIndex > 9) { // arr[i] == 100
            bucketIndex = 9;
        }

        // 放入桶内, 并将相应桶中元素排序
        count[bucketIndex].push_front(arr[i]);
        count[bucketIndex].sort();
    }

    // 合并桶
    for (i = 0; i < bucketNum; i++) {
        tmp = count[i];
        if (tmp.size() > 0) { // 如果某个桶不为空, 输入桶中所有元素
            for (list<int>::iterator iter = tmp.begin(); iter != tmp.end(); iter++) {
                result.push_back(*iter);
            }
        }
    }

    return result;
}

int main(int argc, char *argv[])
{
    int arr[] = {10, 9, 8, 3, 5, 4, 1, 2, 0, 7, 6, 9, 5, 4, 9};
    vector<int> result = bucket_sort(arr, sizeof(arr) / sizeof(int));

    // 0 1 2 3 4 4 5 5 6 7 8 9 9 9 10
    for (vector<int>::iterator iter = result.begin(); iter != result.end(); iter++) {
        cout << *iter << " ";
    }
    cout << endl;

    int arr2[] = {77, 99, 35, 22, 3, 100, 8, 3, 5, 4, 1, 0};
    vector<int> result2 = bucket_sort2(arr2, sizeof(arr2) / sizeof(int));
    // 0 1 3 3 4 5 8 22 35 77 99 100
    for (vector<int>::iterator iter = result2.begin(); iter != result2.end(); iter++) {
        cout << *iter << " ";
    }
    cout << endl;
    return 0;
}
